package com.yanceysong.codetop.s21_s30;

/**
 * @ClassName S23_Mid_300_最长上升子序列
 * @Description
 * @date 2025/09/16
 * @Author yanceysong
 * @Version 1.0
 */
public class S23_Mid_300_最长上升子序列 {
    /**
     * S23_Mid_300_最长上升子序列
     * <p>
     * LeetCode：
     * <a href="https://leetcode.cn/problems/longest-increasing-subsequence/">...</a>
     * <p>
     * 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
     * <p>
     * 子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。
     * 例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
     * <p>
     * 示例 1：
     * <p>
     * 输入：nums = [10,9,2,5,3,7,101,18]
     * 输出：4
     * 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
     * <p>
     * 示例 2：
     * <p>
     * 输入：nums = [0,1,0,3,2,3]
     * 输出：4
     * <p>
     * 示例 3：
     * <p>
     * 输入：nums = [7,7,7,7,7,7,7]
     * 输出：1
     * <p>
     * 提示：
     * <p>
     * 1 <= nums.length <= 2500
     * -10^4 <= nums[i] <= 10^4
     * <p>
     * 使用动态规划求解最长严格递增子序列的长度
     * <p>
     * 算法原理：
     * 1. dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度
     * 2. 对于每个位置 i，检查之前所有位置 j (j < i)
     * 3. 如果 nums[i] > nums[j]，则可以将 nums[i] 接在以 nums[j] 结尾的递增序列后面
     * 4. 状态转移方程：dp[i] = max(dp[i], dp[j] + 1) 其中 j < i 且 nums[i] > nums[j]
     * <p>
     * 核心思想：
     * - 每个元素至少可以单独构成长度为1的递增子序列
     * - 通过比较当前元素与之前所有元素，找出能够形成递增关系的最优解
     * - 维护全局最大值作为最终答案
     * <p>
     * 图解示例：nums = [10,9,2,5,3,7,101,18]
     * <p>
     * 数组索引和值：
     * 索引: 0  1  2  3  4  5   6    7
     * 数值: 10 9  2  5  3  7  101  18
     * <p>
     * 动态规划过程：
     * <p>
     * 初始化：dp = [1, 1, 1, 1, 1, 1, 1, 1]
     * 每个位置初始长度都为1（单独成为一个递增子序列）
     * <p>
     * 处理索引0 (nums[0] = 10)：
     * dp[0] = 1 （基础情况）
     * 当前最大长度 = 1
     * <p>
     * 处理索引1 (nums[1] = 9)：
     * 检查 j=0: nums[1]=9 < nums[0]=10，无法形成递增，dp[1] = 1
     * 当前最大长度 = 1
     * <p>
     * 处理索引2 (nums[2] = 2)：
     * 检查 j=0: nums[2]=2 < nums[0]=10，无法形成递增
     * 检查 j=1: nums[2]=2 < nums[1]=9，无法形成递增
     * dp[2] = 1，当前最大长度 = 1
     * <p>
     * 处理索引3 (nums[3] = 5)：
     * 检查 j=0: nums[3]=5 < nums[0]=10，无法形成递增
     * 检查 j=1: nums[3]=5 < nums[1]=9，无法形成递增
     * 检查 j=2: nums[3]=5 > nums[2]=2，可以形成递增！
     * dp[3] = max(1, dp[2] + 1) = max(1, 1 + 1) = 2
     * 当前最大长度 = 2，递增序列：[2, 5]
     * <p>
     * 处理索引4 (nums[4] = 3)：
     * 检查 j=0: nums[4]=3 < nums[0]=10，无法形成递增
     * 检查 j=1: nums[4]=3 < nums[1]=9，无法形成递增
     * 检查 j=2: nums[4]=3 > nums[2]=2，可以形成递增！
     * dp[4] = max(1, dp[2] + 1) = max(1, 1 + 1) = 2
     * 检查 j=3: nums[4]=3 < nums[3]=5，无法形成递增
     * 当前最大长度 = 2，递增序列：[2, 3]
     * <p>
     * 处理索引5 (nums[5] = 7)：
     * 检查 j=0: nums[5]=7 < nums[0]=10，无法形成递增
     * 检查 j=1: nums[5]=7 < nums[1]=9，无法形成递增
     * 检查 j=2: nums[5]=7 > nums[2]=2，可以形成递增！
     * dp[5] = max(1, dp[2] + 1) = max(1, 1 + 1) = 2
     * 检查 j=3: nums[5]=7 > nums[3]=5，可以形成递增！
     * dp[5] = max(2, dp[3] + 1) = max(2, 2 + 1) = 3
     * 检查 j=4: nums[5]=7 > nums[4]=3，可以形成递增！
     * dp[5] = max(3, dp[4] + 1) = max(3, 2 + 1) = 3
     * 当前最大长度 = 3，递增序列：[2, 5, 7]
     * <p>
     * 处理索引6 (nums[6] = 101)：
     * 检查所有 j < 6，由于101是最大值，都能形成递增
     * 最优选择是接在 dp[5] = 3 后面
     * dp[6] = dp[5] + 1 = 3 + 1 = 4
     * 当前最大长度 = 4，递增序列：[2, 5, 7, 101]
     * <p>
     * 处理索引7 (nums[7] = 18)：
     * 能接在 [2, 5, 7] 后面，但不如 [2, 5, 7, 101] 长
     * dp[7] = 4，但全局最大值仍为4
     * <p>
     * 最终 dp = [1, 1, 1, 2, 2, 3, 4, 4]
     * 最长递增子序列长度 = 4
     * <p>
     * 可视化DP表格：
     * ┌─────┬────┬────┬────┬────┬────┬────┬─────┬────┐
     * │ i   │ 0  │ 1  │ 2  │ 3  │ 4  │ 5  │  6  │ 7  │
     * ├─────┼────┼────┼────┼────┼────┼────┼─────┼────┤
     * │nums │ 10 │ 9  │ 2  │ 5  │ 3  │ 7  │ 101 │ 18 │
     * ├─────┼────┼────┼────┼────┼────┼────┼─────┼────┤
     * │dp   │ 1  │ 1  │ 1  │ 2  │ 2  │ 3  │  4  │ 4  │
     * └─────┴────┴────┴────┴────┴────┴────┴─────┴────┘
     * <p>
     * 时间复杂度：O(n²)，其中 n 是数组长度，需要双重循环
     * 空间复杂度：O(n)，需要 dp 数组存储每个位置的最长递增子序列长度
     * <p>
     * 优化思路：
     * 1. 可以使用二分查找优化到 O(n log n)
     * 2. 使用贪心 + 二分的方法维护一个递增数组
     */
    public int lengthOfLIS(int[] nums) {
        // 边界条件检查
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int arrayLength = nums.length;
        // dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度
        int[] dpLengthArray = new int[arrayLength];
        // 初始化：每个元素单独构成长度为1的递增子序列
        dpLengthArray[0] = 1;

        // 记录全局最长递增子序列的长度
        int globalMaxLength = 1;

        // 从第二个元素开始处理（索引1开始）
        for (int currentIndex = 1; currentIndex < arrayLength; currentIndex++) {
            // 当前位置至少可以单独构成长度为1的递增子序列
            dpLengthArray[currentIndex] = 1;

            // 检查当前元素之前的所有位置
            for (int previousIndex = 0; previousIndex < currentIndex; previousIndex++) {
                // 如果当前元素大于之前的元素，可以形成递增关系
                if (nums[currentIndex] > nums[previousIndex]) {
                    // 状态转移：选择最优的前驱位置
                    // 当前长度 = max(当前长度, 前驱位置长度 + 1)
                    dpLengthArray[currentIndex] = Math.max(
                            dpLengthArray[currentIndex],
                            dpLengthArray[previousIndex] + 1
                    );
                }
            }

            // 更新全局最大长度
            globalMaxLength = Math.max(globalMaxLength, dpLengthArray[currentIndex]);
        }

        return globalMaxLength;
    }

    public static void main(String[] args) {
        S23_Mid_300_最长上升子序列 solution = new S23_Mid_300_最长上升子序列();

        System.out.println("=== 最长递增子序列算法测试开始 ===");

        // 测试1: 题目示例1 - [10,9,2,5,3,7,101,18]
        System.out.println("\n--- 测试1: 经典示例 [10,9,2,5,3,7,101,18] ---");
        testCase1(solution);

        // 测试2: 题目示例2 - [0,1,0,3,2,3]
        System.out.println("\n--- 测试2: 重复元素 [0,1,0,3,2,3] ---");
        testCase2(solution);

        // 测试3: 题目示例3 - [7,7,7,7,7,7,7]
        System.out.println("\n--- 测试3: 相同元素 [7,7,7,7,7,7,7] ---");
        testCase3(solution);

        // 测试4: 边界情况 - 单个元素
        System.out.println("\n--- 测试4: 单个元素 [5] ---");
        testSingleElement(solution);

        // 测试5: 严格递增序列
        System.out.println("\n--- 测试5: 严格递增 [1,2,3,4,5] ---");
        testStrictlyIncreasing(solution);

        // 测试6: 严格递减序列
        System.out.println("\n--- 测试6: 严格递减 [5,4,3,2,1] ---");
        testStrictlyDecreasing(solution);

        // 测试7: 波动序列
        System.out.println("\n--- 测试7: 波动序列 [1,3,2,4,3,5,4,6] ---");
        testFluctuatingSequence(solution);

        // 测试8: 负数测试
        System.out.println("\n--- 测试8: 包含负数 [-1,0,1,2] ---");
        testWithNegativeNumbers(solution);

        // 测试9: 大数值测试
        System.out.println("\n--- 测试9: 大数值 [10000,-10000,5000] ---");
        testLargeNumbers(solution);

        // 测试10: 复杂递增模式
        System.out.println("\n--- 测试10: 复杂模式 [4,10,4,3,8,9] ---");
        testComplexPattern(solution);

        // 测试11: 边界值测试
        System.out.println("\n--- 测试11: 边界值 [-10000,10000] ---");
        testBoundaryValues(solution);

        // 测试12: 长序列测试
        System.out.println("\n--- 测试12: 长序列测试 ---");
        testLongSequence(solution);

        System.out.println("\n=== 所有测试完成 ===");
    }

    /**
     * 测试经典示例：[10,9,2,5,3,7,101,18]
     * 最长递增子序列：[2,3,7,101] 或 [2,5,7,101] 等，长度为4
     */
    private static void testCase1(S23_Mid_300_最长上升子序列 solution) {
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println("输入数组: " + arrayToString(nums));
        printLISVisualization(nums);

        int result = solution.lengthOfLIS(nums);
        System.out.println("lengthOfLIS() -> " + result + " (期望: 4)");
        assert result == 4 : "期望最长递增子序列长度为4";
        System.out.println("✓ 经典示例测试通过");
    }

    /**
     * 测试重复元素：[0,1,0,3,2,3]
     * 最长递增子序列：[0,1,2,3]，长度为4
     */
    private static void testCase2(S23_Mid_300_最长上升子序列 solution) {
        int[] nums = {0, 1, 0, 3, 2, 3};
        System.out.println("输入数组: " + arrayToString(nums));
        printLISVisualization(nums);

        int result = solution.lengthOfLIS(nums);
        System.out.println("lengthOfLIS() -> " + result + " (期望: 4)");
        assert result == 4 : "期望最长递增子序列长度为4";
        System.out.println("✓ 重复元素测试通过");
    }

    /**
     * 测试相同元素：[7,7,7,7,7,7,7]
     * 由于要求严格递增，任何单个元素都不能形成长度>1的递增序列
     */
    private static void testCase3(S23_Mid_300_最长上升子序列 solution) {
        int[] nums = {7, 7, 7, 7, 7, 7, 7};
        System.out.println("输入数组: " + arrayToString(nums));

        int result = solution.lengthOfLIS(nums);
        System.out.println("lengthOfLIS() -> " + result + " (期望: 1)");
        assert result == 1 : "期望最长递增子序列长度为1";
        System.out.println("✓ 相同元素测试通过");
    }

    /**
     * 测试单个元素
     */
    private static void testSingleElement(S23_Mid_300_最长上升子序列 solution) {
        int[] nums = {5};
        System.out.println("输入数组: " + arrayToString(nums));

        int result = solution.lengthOfLIS(nums);
        System.out.println("lengthOfLIS() -> " + result + " (期望: 1)");
        assert result == 1 : "期望最长递增子序列长度为1";
        System.out.println("✓ 单个元素测试通过");
    }

    /**
     * 测试严格递增序列：整个序列就是最长递增子序列
     */
    private static void testStrictlyIncreasing(S23_Mid_300_最长上升子序列 solution) {
        int[] nums = {1, 2, 3, 4, 5};
        System.out.println("输入数组: " + arrayToString(nums));
        printLISVisualization(nums);

        int result = solution.lengthOfLIS(nums);
        System.out.println("lengthOfLIS() -> " + result + " (期望: 5)");
        assert result == 5 : "期望最长递增子序列长度为5";
        System.out.println("✓ 严格递增测试通过");
    }

    /**
     * 测试严格递减序列：只能选择任意单个元素
     */
    private static void testStrictlyDecreasing(S23_Mid_300_最长上升子序列 solution) {
        int[] nums = {5, 4, 3, 2, 1};
        System.out.println("输入数组: " + arrayToString(nums));

        int result = solution.lengthOfLIS(nums);
        System.out.println("lengthOfLIS() -> " + result + " (期望: 1)");
        assert result == 1 : "期望最长递增子序列长度为1";
        System.out.println("✓ 严格递减测试通过");
    }

    /**
     * 测试波动序列：[1,3,2,4,3,5,4,6]
     * 可能的递增子序列：[1,2,3,4,5,6] -> 但实际为 [1,3,4,5,6] 长度为5
     */
    private static void testFluctuatingSequence(S23_Mid_300_最长上升子序列 solution) {
        int[] nums = {1, 3, 2, 4, 3, 5, 4, 6};
        System.out.println("输入数组: " + arrayToString(nums));
        printLISVisualization(nums);

        int result = solution.lengthOfLIS(nums);
        System.out.println("lengthOfLIS() -> " + result + " (期望: 5)");
        assert result == 5 : "期望最长递增子序列长度为5";
        System.out.println("✓ 波动序列测试通过");
    }

    /**
     * 测试包含负数的情况
     */
    private static void testWithNegativeNumbers(S23_Mid_300_最长上升子序列 solution) {
        int[] nums = {-1, 0, 1, 2};
        System.out.println("输入数组: " + arrayToString(nums));
        printLISVisualization(nums);

        int result = solution.lengthOfLIS(nums);
        System.out.println("lengthOfLIS() -> " + result + " (期望: 4)");
        assert result == 4 : "期望最长递增子序列长度为4";
        System.out.println("✓ 负数测试通过");
    }

    /**
     * 测试大数值
     */
    private static void testLargeNumbers(S23_Mid_300_最长上升子序列 solution) {
        int[] nums = {10000, -10000, 5000};
        System.out.println("输入数组: " + arrayToString(nums));
        printLISVisualization(nums);

        int result = solution.lengthOfLIS(nums);
        System.out.println("lengthOfLIS() -> " + result + " (期望: 2)");
        assert result == 2 : "期望最长递增子序列长度为2";
        System.out.println("✓ 大数值测试通过");
    }

    /**
     * 测试复杂递增模式：[4,10,4,3,8,9]
     * 最长递增子序列：[3,8,9] 或 [4,8,9]，长度为3
     */
    private static void testComplexPattern(S23_Mid_300_最长上升子序列 solution) {
        int[] nums = {4, 10, 4, 3, 8, 9};
        System.out.println("输入数组: " + arrayToString(nums));
        printLISVisualization(nums);

        int result = solution.lengthOfLIS(nums);
        System.out.println("lengthOfLIS() -> " + result + " (期望: 3)");
        assert result == 3 : "期望最长递增子序列长度为3";
        System.out.println("✓ 复杂模式测试通过");
    }

    /**
     * 测试边界值
     */
    private static void testBoundaryValues(S23_Mid_300_最长上升子序列 solution) {
        int[] nums = {-10000, 10000};
        System.out.println("输入数组: " + arrayToString(nums));
        printLISVisualization(nums);

        int result = solution.lengthOfLIS(nums);
        System.out.println("lengthOfLIS() -> " + result + " (期望: 2)");
        assert result == 2 : "期望最长递增子序列长度为2";
        System.out.println("✓ 边界值测试通过");
    }

    /**
     * 测试长序列
     */
    private static void testLongSequence(S23_Mid_300_最长上升子序列 solution) {
        // 构造一个长度为50的波动序列
        int[] nums = new int[50];
        for (int i = 0; i < 50; i++) {
            nums[i] = i % 10;  // 0,1,2,...,9,0,1,2,...
        }

        System.out.println("输入: 长度为50的波动序列 [0,1,2,3,4,5,6,7,8,9,0,1,2,...]");
        System.out.println("模式: 每10个数字为一个周期，重复5次");

        int result = solution.lengthOfLIS(nums);
        System.out.println("lengthOfLIS() -> " + result + " (期望: 10)");
        System.out.println("解释: 最长递增子序列为第一轮的 [0,1,2,3,4,5,6,7,8,9]");
        assert result == 10 : "期望最长递增子序列长度为10";
        System.out.println("✓ 长序列测试通过");
    }

    /**
     * 辅助方法：将数组转换为字符串表示
     */
    private static String arrayToString(int[] arr) {
        if (arr.length == 0) return "[]";

        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < arr.length; i++) {
            sb.append(arr[i]);
            if (i < arr.length - 1) {
                sb.append(", ");
            }
        }
        sb.append("]");
        return sb.toString();
    }

    /**
     * 辅助方法：可视化最长递增子序列的DP过程（简化版）
     */
    private static void printLISVisualization(int[] nums) {
        if (nums.length == 0 || nums.length > 10) return;  // 只对较短数组进行可视化

        System.out.println("DP过程可视化:");

        // 打印索引
        System.out.print("索引: ");
        for (int i = 0; i < nums.length; i++) {
            System.out.printf("%3d ", i);
        }
        System.out.println();

        // 打印数值
        System.out.print("数值: ");
        for (int i = 0; i < nums.length; i++) {
            System.out.printf("%3d ", nums[i]);
        }
        System.out.println();

        // 计算并打印DP值
        int[] dp = new int[nums.length];
        dp[0] = 1;

        System.out.print("DP值: ");
        System.out.printf("%3d ", dp[0]);

        for (int i = 1; i < nums.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            System.out.printf("%3d ", dp[i]);
        }
        System.out.println();
        System.out.println();
    }
}
